To alleviate the issues of high complexity and poor scalability in the processing of keyword-aware optimal route query algorithms for large scale graph or multiple query keywords, an effective algorithm was proposed based on the scheme of keyword sequence route generating. The algorithm satisfied the coverage of query keywords first, and took a path expansion inspired by the keyword coverage property rather than aimless adjacent edge expansion to efficiently construct candidate paths. With the aid of a scaling method and ineffective route pruning, the search space was reduced into a polynomial order from an original factorial order, which further reduced the complexity and enhanced the scalability. Experiments conducted over four gragh datasets verified the accuracy and improvement in efficiency and scalability of the proposed algorithm.

Polysemy is an important and pervasive semantic phenomenon in Chinese; the task of word sense induction is to classify words with the same semantics in different contexts, which is a clustering problem essentially. Currently, unsupervised clustering algorithm has been widely used in its research. In this paper, an improved method of k-means was proposed, which mainly improved the selection of initial cluster centers and the calculation of cluster centroid and overcame the “noise” and the sensitivity of isolated point in data to some extent. Another idea was to use the classification coding of word in Tongyici Cilin to reduce the feature dimension. The experimental results show that the performance has great improvement with the improved k-means, of which the F-Score reached 75.8%.